package com.jojo.elementary.day1_array;

/**
 * 53、最大子数组和
 *
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组 是数组中的一个连续部分。
 *
 * 示例 1：
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组[4,-1,2,1] 的和最大，为6 。
 *
 * 示例 2：
 * 输入：nums = [1]
 * 输出：1
 *
 * 示例 3：
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 *
 *进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
 *
 */
public class MaxSubArraySum {

    /** myCode 动态规划*/
    int getMaxSubSum(int[] nums){
        int relMax = nums[0],max = nums[0];  //最大值
        for (int i = 1;i < nums.length;i++){
            max = Math.max(nums[i],max + nums[i]);
            relMax = Math.max(max,relMax);
        }
        return relMax;
    }

    /** pe. 分治 */
    int getMaxSubSum2(int[] nums){
        return getMaxSubArr(nums, 0, nums.length - 1).mSum;
    }

    Status getMaxSubArr(int[] a,int left,int right){
        if (left == right){
            return new Status(a[left],a[left],a[left],a[left]);
        }
        int mid = (left + right) >> 1;
        Status lStatus = getMaxSubArr(a,left,mid);
        Status rStatus = getMaxSubArr(a,mid + 1,right);
        return pushUp(lStatus,rStatus);
    }

    Status pushUp(Status l,Status r){
        //根据左右两个子区间求父区间的四个值
        int lSum = Math.max((l.iSum + r.lSum),l.lSum);
        int rSum = Math.max((r.iSum + l.rSum),r.rSum);
        int mSum = Math.max(Math.max(l.mSum,r.mSum),l.rSum + r.lSum);
        int iSum = l.iSum + r.iSum;
        return new Status(lSum,rSum,mSum,iSum);
    }
    public static void main(String[] args) {
        MaxSubArraySum max = new MaxSubArraySum();
        int[] arr = {-2,-1,-3,-4,-1,-2,-1,-5,-4};
        System.out.println(max.getMaxSubSum(arr));
        System.out.println(max.getMaxSubSum2(arr));
    }
}

class Status{

    /* 分别代表序列a在[l,r]区间内
        以l为左端点的最大子段和，
        以r为右端点的最大子段和，
        [l,r]内的最大子段和，
        [l,r]的区间和
     */
    public int lSum, rSum, mSum, iSum;

    public Status(int lSum, int rSum, int mSum, int iSum) {
        this.lSum = lSum;
        this.rSum = rSum;
        this.mSum = mSum;
        this.iSum = iSum;
    }
}
